package leetcode;



import jdk.nashorn.internal.objects.NativeUint8Array;

import java.util.*;

class MinStack {
    Stack<Integer> stack=null;
    Stack<Integer> minStackk=null;
    public MinStack() {
        stack=new Stack<>();
        minStackk=new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if (minStackk.isEmpty()){
            minStackk.push(val);
        }else {
            if (minStackk.peek()>=val){
                minStackk.push(val);
            }
        }
    }

    public void pop() {
        int val=stack.pop();
        if (!minStackk.isEmpty()&&val==minStackk.peek()){
            minStackk.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int min() {
        return minStackk.peek();
    }
}
public class LeetCodeMain105 {
    public int[] levelOrder(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        if (root!=null){
            queue.offer(root);
        }
        while (!queue.isEmpty()){
            int size=queue.size();
            while (size>0){
                size--;
                TreeNode n=queue.poll();
                list.add(n.val);
                if (n.left!=null){
                    queue.offer(n.left);
                }
                if (n.right!=null){
                    queue.offer(n.right);
                }
            }
        }
        int[] arr=new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            arr[i]=list.get(i);
        }
        return arr;
    }
    public boolean isSymmetric(TreeNode root) {
        if (root==null){
            return true;
        }
        return isTree(root.left,root.right);
    }
    public boolean isTree(TreeNode left,TreeNode right){
        if (left==null&&right==null){
            return true;
        }
        if ((left==null&&right!=null)||(right==null&&left!=null)){
            return false;
        }
        if (left!=null&&right!=null&&right.val!=left.val){
            return false;
        }
        return isTree(left.left, right.right)&&isTree(left.right, right.left);
    }
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = mirrorTree(root.left);
        TreeNode right = mirrorTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if (popped.length==0||popped==null){
            return true;
        }
        Stack<Integer> stack=new Stack<>();
        int length=popped.length;
        int count=0;
        for (int i = 0; i < length; i++) {
            stack.add(pushed[i]);
            while (!stack.isEmpty()&&stack.peek()==popped[count]){
                count++;
                stack.pop();
            }
        }
        if (stack.isEmpty()){
            return true;
        }
        return false;
    }
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode n1=null;
        ListNode n2=head;
        ListNode n3=head.next;
        while (n2!=null){
            n2.next=n1;
            n1=n2;
            n2=n3;
            if (n3!=null){
                n3=n3.next;
            }

        }
        return n1;
    }

}